class Solution {
public:   //单调性+双指针
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;  
        sort(nums.begin(), nums.end());  //先排序

        int n = nums.size();
        for (int i = 0; i < n; ) {  //先固定一个数nums[i]
            //小优化 
            if(nums[i] > 0) break;

            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {  //利用双指针算法找出两数和为-nums[i]
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else 
                {
                    ret.push_back({nums[left], nums[right], nums[i]});
                    //找到一种结果后，不要"停"，继续往后找
                    left++, right--;
                    //处理"越界情况" + 去重
                    while (left < right && nums[left] == nums[left - 1])  left++;  //left跳过重复的元素
                    while (left < right && nums[right] == nums[right + 1])  right--; //right跳过重复的元素
                }
            }

            i++;
            //i跳过重复的元素
            while(i < n && nums[i - 1] == nums[i]) i++;
        }

        return ret;
    }
}